Giga Games 1/Giga Games.iso/net/go/games/optimal.sh

Linux/UNIX/POSIX Shell Script | 1993-06-20 | 8.7 KB | 411 lines

#! /bin/sh
# This is a shell archive, meaning:
# 1. Remove everything above the #! /bin/sh line.
# 2. Save the resulting text in a file.
# 3. Execute the file with /bin/sh (not csh) to create:
#    README
#    opt1
#    opt2
#    opt3
#    opt4
#    opt5
#    opt6
#    opt7
# This archive created: Mon Jan 20 18:43:13 1992
export PATH; PATH=/bin:/usr/bin:$PATH
if test -f 'README'
then
    echo shar: "will not over-write existing file 'README'"
else
cat << \SHAR_EOF > 'README'
Path: milton!usenet.coe.montana.edu!rpi!usc!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!jvnc.net!darwin.sura.net!europa.asd.contel.com!uunet!mcsun!sun4nl!cwi.nl!tromp
From: [e-mail] (John Tromp)
Newsgroups: rec.games.go
Subject: supposedly optimal play on small go-boards
Message-ID: <[e-mail]>
Date: 14 Jan 92 13:35:43 GMT
Sender: [e-mail]
Organization: CWI, Amsterdam
Lines: 343

Recently, I got interested in discovering optimal play in go.
That is, assuming the best play by both black and white, by how
many points can black win the game? Since I have little hope of
answering this question for the usual 19x19 board, or even the 9x9 one,
I'll restrict my attention to board sizes smaller than 9x9.

The answer of course depends on the exact scoring rules used.
The rules I use here are to count empty territory + prisoners, as
the program mgt does it.
Hopefully other readers will comment on changes in the outcome caused
by different scoring rules (e.g. chinese).

Attached to this message is a shar file containing 7 files in mgt format.
The first 6, on board sizes ranging from 1x1 through 6x6 represent what
I believe to be optimal play, while the 7th is just a possible play on
a 7x7 board, in which either white or black is likely to have missed a
better move.
Those lacking the mgt program can also follow the lines by numbering both
axes of the board alphabetically.

The outcomes I get are:

boardsize            1x1  2x2  3x3  4x4  5x5  6x6  7x7
margin for black       0    0    8    1   24    3    8

The first two are rather silly but included anyway for completeness.
Note that on the 3x3 and 5x5 boards, black effectively dominates the whole
board by playing in the center and thus wins by nxn-1. In the games, I have
let white play as long as black is forced to reply.

I would like to have your opinion on these games, in particular
suggestions for better lines in the 7x7 game. The 8x8 board may
also be amenable to such analysis due to the symmetry. Still, it's not
so obvious that one should start dividing the center, which in this
case is relatively far from the edge.

Happy analysis!

-John Tromp, ~10 kyu ([e-mail])





Path: milton!nntp.uoregon.edu!cs.uoregon.edu!mips!think.com!wupost!waikato.ac.nz!comp.vuw.ac.nz!canterbury.ac.nz!math!wft
From: [e-mail] (Bill Taylor)
Newsgroups: rec.games.go
Subject: Optimal play on small go-boards.
Message-ID: <[e-mail]>
Date: 20 Jan 92 05:26:30 GMT
Organization: Department of Mathematics, University of Canterbury
Lines: 59
Nntp-Posting-Host: math.canterbury.ac.nz

[e-mail] (John Tromp) posted an article "supposedly optimal play on small
go-boards" on 14 Jan 92.

I was hoping there would be some replies, but none so far, so here's mine.

John writes
> The outcomes I get are:
>
> boardsize            1x1  2x2  3x3  4x4  5x5  6x6  7x7
> margin for black       0    0    8    1   24    3    8

He is using (empty spaces + prisoners) scoring, which is in fact neither
Chinese nor Japanese. My comments will be directed mainly toward Chinese scoring,
(as suggested by John), i.e. 1 point for all intersections filled or surrounded,
(ignoring prisoners), which I understand is also official American scoring now
as well. (It has been official here in N.Z. for many years). With this we get

boardsize           2x2  3x3  4x4  5x5  6x6
margin for black      1    9    2   25    4

with the same moves as given by John. These figures are all one point more to
black, (as is the case in 50% of normal games; interestingly for these small
boards this happens in ALL cases, black always gets the last move.)
                                                               a   b
Only the case 2x2 needs a little extra comment. The full
game should go (aa bb ba pass pass). Thus black is ahead    a  @ - .
by one point, as in the diagram. White cannot improve with     |   |
capture ab, otherwise black plays ba (NOT aa !), then       b  @ - O
aa ba ab aa pass, and white cannot play, by the (Chinese
and American) no-repeat rule. These comments, and the cases 3x3 and 4x4, were
given by James Davies, in his article "the Chinese rules of go", in GO WORLD
of about late '77 or early '78.

The 4x4 case needs a little checking, but is fairly straightforward; (as Davies
points out, this is in fact a zero-point tie in Japanese).           The 3x3
and 5x5 cases are very simple, and could sensibly end after only one move, of
course (especially the 3x3). The 6x6 case is more interesting; the line
given by John is correct, as given in an introductory go book whose name
I've unfortunately forgotten (if anyone has seen this book I'd be grateful for
an email on this !). John gives cc dd dc cd bd be ed ee de ce fe ef ec bc bb
ad ab ac fd df ff. This gives 4 (Chinese) to black, the best result. The moves
for black are all forced (ignoring trivial symmetries); but White has some
interesting options that give the same final score with correct play. You
might have some fun checking out the variant where white plays mirror-go for
as long as he can, and black must find the correct way to break out of it.

As for the 7x7, I suspect John's answer of 8 (Chinese 9) is wrong. John gives
a line starting dd ee ed de cd , then continuing much as in the 6x6 case, giving
the result above. However I suspect black's 3rd move is wrong. With the more
aggressive 3rd move, ce, we get, for the whole game, in its most simple
variant; dd ee ed de ce cf be bf fe ff fd bd cd ae bc ad ac af gf fg ge dg gg.
Black wins by 15 (14 Japanese); but white may resist more strongly at various
places, and it then becomes quite hard to check that black can maintain this
result. I suspect that a fully detailed analysis would cover several pages to
be reasonably convincing !

Anyway, all players are urged to try for themselves, and post their comments
for us to see.
----------------------Pleasant plonking!------Bill Taylor--------------------

SHAR_EOF
fi
if test -f 'opt1'
then
    echo shar: "will not over-write existing file 'opt1'"
else
cat << \SHAR_EOF > 'opt1'
(
;
GaMe[1]
VieW[]
SiZe[1]
Comment[Black: 0 + 0 = 0

White: 0 + 0 = 0

White wins by 0.]
)
SHAR_EOF
fi
if test -f 'opt2'
then
    echo shar: "will not over-write existing file 'opt2'"
else
cat << \SHAR_EOF > 'opt2'
(
;
GaMe[1]
VieW[]
SiZe[2]
Comment[A supposedly optimal game.]
;
Black[aa]
;
Comment[Black: 0 + 0 = 0

White: 0 + 0 = 0

White wins by 0.]
White[bb]
)
SHAR_EOF
fi
if test -f 'opt3'
then
    echo shar: "will not over-write existing file 'opt3'"
else
cat << \SHAR_EOF > 'opt3'
(
;
GaMe[1]
VieW[]
SiZe[3]
Comment[A supposedly optimal game.]
;
Black[bb]
;
White[bc]
;
Black[cb]
;
White[ab]
;
Comment[Black: 6 + 2 = 8

White: 0 + 0 = 0

Black wins by 8.]
Black[ba]
)
SHAR_EOF
fi
if test -f 'opt4'
then
    echo shar: "will not over-write existing file 'opt4'"
else
cat << \SHAR_EOF > 'opt4'
(
;
GaMe[1]
VieW[]
SiZe[4]
Comment[A supposedly optimal game.]
;
Black[bb]
;
White[cc]
;
Black[cb]
;
White[bc]
;
Black[ac]
;
White[db]
;
Black[bd]
;
White[ca]
;
Black[cd]
;
White[dc]
;
Comment[Black: 2 + 0 = 2

White: 1 + 0 = 1

Black wins by 1.]
Black[aa]
)
SHAR_EOF
fi
if test -f 'opt5'
then
    echo shar: "will not over-write existing file 'opt5'"
else
cat << \SHAR_EOF > 'opt5'
(
;
GaMe[1]
VieW[]
SiZe[5]
Comment[A supposedly optimal game.]
;
Black[cc]
;
White[cd]
;
Black[dc]
;
White[bc]
;
Black[bb]
;
White[ad]
;
Comment[Black: 21 + 3 = 24

White: 0 + 0 = 0

Black wins by 24.]
Black[be]
)
SHAR_EOF
fi
if test -f 'opt6'
then
    echo shar: "will not over-write existing file 'opt6'"
else
cat << \SHAR_EOF > 'opt6'
(
;
GaMe[1]
VieW[]
SiZe[6]
Comment[A supposedly optimal game.]
;
Black[cc]
;
White[dd]
;
Black[dc]
;
White[cd]
;
Black[bd]
;
White[be]
;
Black[ed]
;
White[ee]
;
Black[de]
;
White[ce]
;
Black[fe]
;
White[ef]
;
Black[ec]
;
White[bc]
;
Black[bb]
;
White[ad]
;
Black[ab]
;
White[ac]
;
Black[fd]
;
White[df]
;
Comment[Black: 11 + 0 = 11

White: 6 + 2 = 8

Black wins by 3.]
Black[ff]
)
SHAR_EOF
fi
if test -f 'opt7'
then
    echo shar: "will not over-write existing file 'opt7'"
else
cat << \SHAR_EOF > 'opt7'
(
;
GaMe[1]
VieW[]
SiZe[7]
Comment[A supposedly optimal game.]
;
Black[dd]
;
White[ee]
;
Black[ed]
;
White[de]
;
Black[cd]
;
White[ce]
;
Black[be]
;
White[bf]
;
Black[fe]
;
White[ff]
;
Black[fd]
;
White[bd]
;
Black[bc]
;
White[ae]
;
Black[ac]
;
White[gf]
;
Black[ad]
;
White[be]
;
Comment[Black: 20 + 0 = 20

White: 11 + 1 = 12

Black wins by 8.]
Black[ge]
)
SHAR_EOF
fi
exit 0
#    End of shell archive